/**
 * https://leetcode.cn/problems/string-compression-ii/submissions/
 * 1531.压缩字符串
 * difficulty 2024.11.09
 * 多维dp
 */

const int INF = 0x3f3f3f3f;
class Solution {
public:
    inline int len(int k){
        if(k <= 1) return 0;
        else if(k > 1 && k < 10) return 1;
        else if(k >= 10 && k < 100) return 2;
        else return 3;
    }

    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(k+1,INF));
        dp[0][0] = 0;

        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= k && j <= i; ++j){
                if(j < k) dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]);
                int same = 0;
                int del = 0;
                for(int m = i; m <= n; ++m){
                    if(s[m-1] == s[i-1]) same++;
                    else del++;
                    if(j + del <= k){
                        dp[m][j+del] = min(dp[m][j+del],len(same) + 1 + dp[i-1][j]);
                    }else{
                        break;
                    }
                }
            }
        }

        return dp[n][k];
    }
};